#include <bits/stdc++.h>

using namespace std;

// 和至少为K的最短子数组
// 给定一个数组arr，其中的值有可能正、负、0
// 给定一个正数k
// 返回累加和>=k的所有子数组中，最短的子数组长度
// 测试链接 : https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/

class Solution 
{
private:
    static const int MAXN = 100001;
    long q[MAXN];
    int h, t;

public:
    int shortestSubarray(vector<int>& nums, int k) 
    {
        long n = nums.size(), ret = n + 1;
        long sum[n + 1];
        sum[0] = 0;
        for(int i = 0; i < n; ++i) sum[i + 1] = sum[i] + nums[i];

        h = t = 0;
        for(int i = 0; i <= n; ++i)
        {
            // 前0个数前缀和
			// 前1个数前缀和
			// 前2个数前缀和
			// ...
			// 前n个数前缀和
            while(h < t && sum[i] - sum[q[h]] >= k)
            {
                // 如果当前的前缀和 - 头前缀和，达标！
                ret = min(ret, i - q[h++]);
            }
            // 前i个数前缀和，从尾部加入
			// 小 大
            while(h < t && sum[i] <= sum[q[t - 1]]) --t;
            q[t++] = i;
        }

        return ret > n ? -1 : ret;
    }
};